package com.bee.剑指offer;

/**
 * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
 *
 * @version 1.0.0
 * @Author yong.Mr
 * @data 2021-04-17
 */
public class 树的子结构 {

    /**
     * 遍历A树，寻找A树的子结点和B树的根结点相等，
     * 以A树中匹配的叶子结点为根结点的子树，于B树进行比较，(左子树，右子树每一个结点都必须比较)
     * 判定条件：
     * 1，root2(B)数遍历为null认为遍历完成，返回true
     * 2，root2不为null,root1(A子树)遍历出现null，返回false
     * 3，值不相等的，返回false
     */
    public static boolean HasSubtree(TreeNode A, TreeNode B) {
        if(A == null) {
            return Boolean.FALSE;
        }
        if(B == null){
            return Boolean.FALSE;
        }
        if(A.val == B.val) {
            if(judgeTree(A, B)){
                return Boolean.TRUE;
            }
        }
        return HasSubtree(A.left, B) || HasSubtree(A.right, B);
    }

    public static Boolean judgeTree(TreeNode root1, TreeNode root2) {
        // 将root2树遍历完成，说明root2树是root1的子树结构，直接返回true
        if(root2 == null) {
            return Boolean.TRUE;
        }
        if(root1 == null) {
            return Boolean.FALSE;
        }
        if(root1.val == root2.val) {
            return judgeTree(root1.left,root2.left) && judgeTree(root1.right,root2.right);
        }
        return Boolean.FALSE;
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(8);
        A.left = new TreeNode(8);
        A.right = new TreeNode(7);
        A.left.left = new TreeNode(9);
        A.left.right = new TreeNode(3);
        A.left.left.left = new TreeNode(4);
        A.left.left.right = new TreeNode(7);
        TreeNode B = new TreeNode(8);
        B.left = new TreeNode(9);
        B.right = new TreeNode(2);
        boolean flag = HasSubtree(A, B);
        System.out.println(flag);
    }
}

class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }
}
